﻿#include <iostream>
using namespace std;

const int m = 6;
const int n = 9;
int L[m + 1][n + 1] = { 0 };
int S[m + 1][n + 1] = { 0 };
char x[m] = { 'a', 'b', 'c', 'b', 'd', 'b' };
char y[n] = { 'a', 'c', 'b', 'b', 'a', 'b', 'd', 'b', 'b' };

int commonOrder(char x[], int m, char y[], int n, char z[]) {
	int i, j, k;
	/*
	for(j = 0; j <= n; j++){
		L[0][j] = 0;
	}
	for(i = 0; i <= m; i ++){
		L[i][0] = 0;
	}
	*/
	for(i = 1; i <= m; i++) {
		for(j = 1; j <= n; j++) {
			if(x[i - 1] == y[j - 1]) {
				L[i][j] = L[i - 1][j - 1] + 1;
				S[i][j] = 1;
			} else if(L[i][j - 1] >= L[i - 1][j]) {
				L[i][j] = L[i][j - 1];
				S[i][j] = 2;
			} else {
				L[i][j] = L[i - 1][j];
				S[i][j] = 3;
			}
		}
	}
	i = m;
	j = n;
	k = L[m][n];
	while(i > 0 && j > 0) {
		if(S[i][j] == 1) {
			z[k - 1] = x[i - 1];
			k--;
			i--;
			j--;
		} else if(S[i][j] == 2) {
			j--;
		} else {
			i--;
		}
	}
	for(k = 0; k < L[m][n]; k++) {
		cout << z[k];
	}

	return L[m][n];
}

int main() {
	char z[15] = {0};
	cout << endl << "公共子序列长度：" << commonOrder(x, m, y, n, z) << endl;

	system("pause");
	return 0;
}